package 三数之和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 三数之和
 * @date 2022/10/23 11:11
 */
public class Demo15 {
    public List<List<Integer>> threeSum(int[] nums) {
        //排序
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        for (int i = 0; i < nums.length-1; i++) {
            //如果当前的一个数字已经大于0.则直接返回 ****裁剪
            if(nums[i]>0){
                return res;
            }
            //如果当前数字和上一个数字相同，则跳过 *** 裁剪
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right= nums.length-1;
            while (left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else {
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //在left小于right的前提下，nums[left+1] 一定不会越界
                    while (left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    //在left小于right的前提下，nums[right-1] 一定不会越界
                    while (left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return res;

    }
}
